HW#5 --- last modified February 06 2019 04:07:42..

Solution set.

Due date: May 15

Files to be submitted:
  Hw5.zip

Purpose: To gain experience with randomized complexity classes, interactive protocols, and circuit lower bounds.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO4 -- Know properties of the randomized classes RP, BPP.

LO6 -- Be able to explain interactive proof characterizations of classes like PSPACE.

LO7 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits or switching lemma techniques.

Specification:

For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw5.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.

1. Prove BPL, bounded-error probabilistic logspace, is contained in L/poly.
2. Prove that if `L_1 and L_2` are two languages in `C` where `C` is either `RP` or `BPP`, then so are `L_1 \cap L_2` and `L_1 \cup L_2`.
3. Prove `IP subseteq PSPACE`.
4. Prove `MA subseteq AM[2]`.
5. Consider the circuit `MOD_3(x_1, x_3) ^^ (x_5 vv neg MOD_3(x_2, x_4))`. Explicitly work out an approximating polynomial for this circuit given by the proof of Razborov-Smolensky. When you pick random subsets, give me the info so I can understand how you did it.

Point Breakdown